/*
 * @lc app=leetcode.cn id=117 lang=cpp
 * @lcpr version=30204
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        // if (root == nullptr) { // 处理空树情况
        //     return root;
        // }

        // queue<Node*> q;
        // q.push(root);

        // while(!q.empty()) {
        //     int size = q.size();    // 当前层的个数

        //     Node* prev = nullptr;
        //     for(int i = 0; i < size; ++i) {
        //         Node* current = q.front();
        //         q.pop();

        //         // 将子节点加入队列（关键修复：确保所有非空子节点都入队）
        //         if (current->left != nullptr) {
        //             q.push(current->left);
        //         }
        //         if (current->right != nullptr) {
        //             q.push(current->right);
        //         }
                
        //         if (i != 0) {
        //             prev->next = current;
        //         }
        //         prev = current;

        //     }
        // }
        // return root;

        // 法二：
        Node dummy;
        Node* cur = root;
        while(cur) {
            dummy.next = nullptr;
            Node* tail = &dummy;    // 下一层链表的尾节点，初始为空，设置为哨兵节点
            while(cur) {
                if (cur->left) {
                    tail->next = cur->left;
                    tail = tail->next;
                }
                if (cur->right) {
                    tail->next = cur->right;
                    tail = tail->next;
                }
                cur = cur->next;
            }
            cur = dummy.next;
        }

        return root;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [1,2,3,4,5,null,7]\n
// @lcpr case=end

// @lcpr case=start
// []\n
// @lcpr case=end

 */

